package algorithm.heap;

public class IndexMaxHeap {


    private Integer[] data;
    //对应的节点在树中的位置
    private Integer[] indexs;
    //
    private Integer[] reverse;

    private int capacity;

    private int count;

    public IndexMaxHeap(int capacity) {
        this.capacity = capacity+1;
        data = new Integer[ this.capacity];
        indexs = new Integer[ this.capacity];
        reverse = new Integer[ this.capacity];

    }


    public IndexMaxHeap(Integer[] data, int capacity){
        this(capacity);
        for (int i = 0; i < data.length; i++) {
            this.data[i+1]=data[i];
            count++;
        }
        for (int i = count / 2 ; i >0; i--) {
            shiftDown(i);
        }
    }


    private int getCount() {
        return count;
    }


    public void put(Integer item) {
        if (count >= capacity) {
            throw new RuntimeException("超出容量限制");
        }
        data[++count] = item;
        indexs[count] = count;
        reverse[count] = count;
        shiftUp(item, count);

    }

    private void shiftUp(Integer item, int index) {
        while (index > 1 && data[indexs[index / 2]] < data[indexs[index]]) {
            swap(indexs, index / 2, index);
            swap(reverse,indexs[index / 2],indexs[index]);
            index = index / 2;
        }
    }


    public Integer pop() {
        Integer item = data[indexs[1]];
        indexs[1] = indexs[count--];
        reverse[indexs[1]] = reverse[indexs[count]];
        shiftDown(1);
        return item;
    }

    private void shiftDown(int index) {
        while (index*2<=count){
            int j = index*2;
            if (index*2+1<=count&&data[indexs[index*2+1]]>data[indexs[index*2]]){
                j++;
            }
            if (data[indexs[index]]<data[indexs[j]]){
                swap(indexs,index,j);
                swap(reverse,indexs[index ],indexs[j]);
                index=j;
            }else{
                break;
            }
        }
    }


    private void swap(Integer[] arr, int i, int j) {
        int tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    public static void main(String[] args) {
        IndexMaxHeap maxHeap = new IndexMaxHeap(10);
        maxHeap.put(1);
        maxHeap.put(2);
        maxHeap.put(3);
        maxHeap.put(4);
        maxHeap.put(5);
        maxHeap.put(7);
        maxHeap.put(8);
        maxHeap.put(9);
        maxHeap.put(19);
        maxHeap.put(22);
        for (int i = 0; i < 10; i++) {
            System.out.println(maxHeap.pop());
        }

    }
}
